class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
    	if (height.size() == 0) {
			return 0;
		}
		int n = height.size();
		vector<int> left(n);
		vector<int> right(n);
		stack<int> stk;

		for (int i = 0; i < n; ++i) {
			if (i == 0) {
				left[i] = i;
			} else {
				while (!stk.empty() && height[stk.top()] >= height[i]) {
					stk.pop();
				}
				if (stk.empty()) {
					left[i] = 0;
				} else {
					left[i] = stk.top() + 1;
				}
			}
			stk.push(i);
		}

		while (!stk.empty()) {
			stk.pop();
		}

		for (int i = n - 1; i >= 0; --i) {
			if (i == n - 1) {
				right[i] = i;
			} else {
				while (!stk.empty() && height[stk.top()] >= height[i]) {
					stk.pop();
				}
				if (stk.empty()) {
					right[i] = n - 1;
				} else {
					right[i] = stk.top() - 1;
				}
			}
			stk.push(i);
		}

		int ans = 0;
		for (int i = 0; i < n; ++i) {
			int t = height[i] * (right[i] - left[i] + 1);
			if (t > ans) {
				ans = t;
			}
		}
		return ans;

    }
};